//https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=23451&ru=%2Fpractice%2F8b3b95850edb4115918ecebdf1b4d222&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26tpId%3D13%26type%3D13
// 思路1:把多种情况都考虑清楚即可；//后继节点
// 情况1:1.有右子树，找到右子树的最左节点；2.无右子树，当前节点是父亲节点的左孩子 3.无右子树，当前节点是父亲节点的右孩子
#include <algorithm>
#include <climits>
#include <queue>
#include <vector>
#include <stack> 
#include <limits>

using namespace std;

struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
        
    }
};

class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode) {
        if(pNode == nullptr) return nullptr;
        TreeLinkNode* res_node = nullptr;
        if (pNode->right) {
            // 右子树的最左节点
            TreeLinkNode* cur_node = pNode->right;
            while(cur_node->left != nullptr) {
                cur_node = cur_node->left;
            }
            res_node = cur_node;
        } else if (pNode->right == nullptr &&  pNode->next == nullptr) {
            res_node = nullptr;
        } else if (pNode->next != nullptr && pNode->next->left == pNode) {
            res_node = pNode->next;
        } else if (pNode->next != nullptr && pNode->next->right == pNode) {
            // 向上找一直找到父亲是爷爷节点的左孩子
           TreeLinkNode* cur_node = pNode->next;
           while (cur_node) {
            if (cur_node->next) {
                if (cur_node->next->left == cur_node) {
                    cur_node = cur_node->next;
                    break;
                } else {
                    cur_node = cur_node->next;
                }
            }else {
                cur_node = nullptr;
            }
           }
           res_node = cur_node;
        }
        return res_node;
    }
};